The parent pointers from the BFS trace form a tree structure, showing the shortest path from the start node to all others.
- From the trace, we can populate the final
levelandparentfor each node. - The
parentpointers define a BFS tree rooted at the start node,s. - This tree contains the shortest path (in terms of edge count) from
sto every other reachable node. - Edges in the original graph that are part of the BFS tree are called tree edges.
- Other edges, which connect nodes at the same or adjacent levels but aren't part of the shortest path tree, are called non-tree edges.
| Vertex (v) | parent[v] | level[v] |
|---|---|---|
| A | NIL | 0 |
| B | A | 1 |
| C | A | 1 |
| D | B | 2 |
| E | C | 2 |
| F | B | 2 |